#include<bits/stdc++.h>
using namespace std;
const int NN=5e5+4;
vector<int>g[NN];
vector<pair<int,int> >change;
int fa[NN],top[NN],son[NN],siz[NN],dfn[NN],tim,d[NN],idfn[NN];
bool vis[NN];
void dfs1(int u,int f)
{
	vis[u]=true;
	fa[u]=f;
	siz[u]=1;
	d[u]=d[f]+1;
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if(v==f)
			continue;
		if(vis[v])
		{
			if(d[v]<d[u])
				change.push_back({u,v});
			continue;
		}
		dfs1(v,u);
		if(siz[v]>siz[son[u]])
			son[u]=v;
		siz[u]+=siz[v];
	}
}
void dfs2(int u,int t)
{
	vis[u]=true;
	top[u]=t;
	dfn[u]=++tim;
	idfn[tim]=u;
	if(son[u])
		dfs2(son[u],t);
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if(vis[v])
			continue;
		dfs2(v,v);
	}
}
struct segment_tree
{
	int l,r,val,w,addv,addw;
	bool flag;
}tr[NN<<2];
void pushup(int u)
{
	tr[u].flag=tr[u<<1].flag|tr[u<<1|1].flag;
}
void build(int u,int l,int r)
{
    tr[u]={l,r,0,0,0,0};
    if(l==r)
        return;
    int mid=l+(r-l)/2;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
}
void update(int u,int addv,int addw)
{
	tr[u].val+=addv,tr[u].addv+=addv;
	tr[u].w+=addw,tr[u].addw+=addw;
}
void pushdown(int u)
{
	update(u<<1,tr[u].addv,tr[u].addw);
	update(u<<1|1,tr[u].addv,tr[u].addw);
	tr[u].addv=tr[u].addw=0;
}
void modify(int u,int l,int r,int addv,int addw)
{
    if(tr[u].l>=l&&tr[u].r<=r)
    {
    	update(u,addv,addw);
        return;
    }
    pushdown(u);
    int mid=tr[u].l+(tr[u].r-tr[u].l)/2;
    if(l<=mid)
        modify(u<<1,l,r,addv,addw);
    if(r>mid)
        modify(u<<1|1,l,r,addv,addw);
}
void modify_path(int u,int v,int addv,int addw)
{
    while(top[u]!=top[v])
    {
        if(d[top[u]]<d[top[v]])
            swap(u,v);
        modify(1,dfn[top[u]],dfn[u],addv,addw);
        u=fa[top[u]];
    }
    if(d[u]>d[v])
        swap(u,v);
    modify(1,dfn[u]+1,dfn[v],addv,addw);
}
int get_len(int u,int v)
{
	int res=d[u]+d[v];
    while(top[u]!=top[v])
    {
        if(d[top[u]]<d[top[v]])
            swap(u,v);
        u=fa[top[u]];
    }
    if(d[u]>d[v])
    	swap(u,v);
    return res-2*d[u];
}
bool query(int u,int l,int r)
{
	if(tr[u].l>=l&&tr[u].r<=r)
		return tr[u].flag;
	bool res=false;
	int mid=tr[u].l+(tr[u].r-tr[u].l)/2;
	if(l<=mid)
		res|=query(u<<1,l,r);
	if(r>mid)
		res|=query(u<<1|1,l,r);
	return res;
}
int get_first(int L,int R)
{
	int l=L,r=R;
	while(l<r)
	{
		int mid=l+(r-l)/2;
		if(!query(1,L,mid))
			l=mid+1;
		else
			r=mid;
	}
	return idfn[l];
}
int get_last(int L,int R)
{
	int l=L,r=R;
	while(l<r)
	{
		int mid=l+(r-l+1)/2;
		if(!query(1,mid,R))
			r=mid-1;
		else
			l=mid;
	}
	return idfn[l];
}
void query_path(int u,int v)
{
	pair<int,int>pl={-1,-1},pr={-1,-1};
	while(top[u]!=top[v])
    {
        if(d[top[u]]<d[top[v]])
            swap(u,v),swap(pl,pr);
        if(pl.first==-1&&query(1,dfn[top[u]],dfn[u]))
        	pl={dfn[top[u]],dfn[u]};
        u=fa[top[u]];
    }
    if(d[u]>d[v])
        swap(u,v),swap(pl,pr);
    if(pl.first==-1&&query(1,dfn[u]+1,dfn[v]))
    	pl={dfn[u]+1,dfn[v]};
    if(pr.first==-1)
    	pr=pl;
    if(pl.first==-1)
    	pl=pr;
    if(pl.first==-1)
    	return;
	int a=get_first(pl.first,pl.second),b=get_last(pl.first,pl.second),c=get_first(pr.first,pr.second),d=get_last(pr.first,pr.second);
	printf("%d %d %d %d\n",a,b,c,d);
	maxx3=max(maxx3,max(max(get_len(a,c),get_len(a,d)),max(get_len(b,c),get_len(b,d))));
}
set<int>st[NN][2];
void calc(int w)
{
	maxx3=max(maxx3,w*(n-w));
}
void dfs_seg(int u)
{
	if(tr[u].l==tr[u].r)
	{
		if(!tr[u].val)
		{
			if(tr[u].w>=maxx1)
			{
				maxx2=maxx1;
				maxx1=tr[u].w;
			}
			else
				maxx2=max(maxx2,tr[u].w);
		}
		else if(tr[u].val==1)
		{
			maxx3=max(maxx3,tr[u].w);
			int sz=siz[idfn[tr[u].l]];
			auto it=st[tr[u].p].lower_bound(sz+n/2);
			if(it!=st.end())
				calc(*it-sz);
			if(it!=st.begin())
			{
				it--;
				calc(*it,sz);
			}
			it=st[tr[u].p].lower_bound(sz-n/2);
			if(it!=st.end())
				calc(*it,sz);
			if(it!=st.begin())
			{
				it--;
				calc(*it,sz);
			}
			st[tr[u].p].insert(sz);
		}
		return;
	}
	pushdown(u);
	dfs_seg(u<<1),dfs_seg(u<<1|1);
}
int main()
{
	srand(time(0));
	int n,m,k,r;
	scanf("%d%d%d%d",&n,&m,&k,&r);
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs1(1,0);
	memset(vis,false,sizeof(vis));
	dfs2(1,1);
	build(1,1,n);
	for(int i=0;i<change.size();i++)
		modify_path(change[i].first,change[i].second,1,0);
	for(int i=1;i<=k;i++)
	{
		int s,t;
		scanf("%d%d",&s,&t);
		modify_path(s,t,0,1);
	}
	dfs_seg(1);
	for(int i=0;i<change.size();i++)
		query_path(change[i].first,change[i].second);
	if(r==1)
		printf("%d",maxx1);
	else
		printf("%d",max(maxx1+maxx2,maxx3));
	return 0;
}
